#define  _CRT_SECURE_NO_WARNINGS
// class Solution {
// public:
//     int maxProduct(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 1) return nums[0];
//         vector<int> f(n + 1), g(n + 1);
//         f[0] = g[0] = 1;
//         for(int i = 1; i <= n; i++)
//         {
//             int cur = nums[i - 1];
//             if(cur < 0)
//             {
//                 g[i] = min(cur, cur * f[i - 1]);
//                 f[i] = max(0, cur * g[i - 1]);
//             }
//             else
//             {
//                 g[i] = cur * g[i - 1];
//                 f[i] = max(cur * f[i - 1], cur);
//             }
//         }
//         int ret = f[1];
//         for(int i = 1; i <= n; i++)
//         {
//             ret = max(f[i], ret);
//         }
//         return ret;
//     }
// };

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        f[0] = g[0] = 1;
        int ret = nums[0];
        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1], x = cur * f[i - 1], y = cur * g[i - 1];
            f[i] = max(cur, max(x, y));
            g[i] = min(cur, min(x, y));
            ret = max(f[i], ret);
        }
        return ret;
    }
};